Write a program to implement a queue using two stacks.

Question

Aryan Kumar · Answer

#include andlt;stdio.h>
#include andlt;stdlib.h>
#define MAXSIZE 100
int stack1[MAXSIZE], stack2[MAXSIZE];
int top1 = -1, top2 = -1;
void enqueue(int data) {
   if (top1 == MAXSIZE - 1) {
       printf("Queue is full, cannot enqueue.
");
       return;
   }
   stack1[++top1] = data;
}
int dequeue() {
   if (top1 == -1 andand top2 == -1) {
       printf("Queue is empty, cannot dequeue.
");
       return -1;
   }
   if (top2 == -1) {
       while (top1 != -1) {
           stack2[++top2] = stack1[top1--];
       }
   }
   int data = stack2[top2--];
   return data;
}
int main() {
   enqueue(1);
   enqueue(2);
   enqueue(3);
   printf("%d ", dequeue());
   printf("%d ", dequeue());
   printf("%d ", dequeue());
   enqueue(4);
   enqueue(5);
   printf("%d ", dequeue());
   printf("%d
", dequeue());
   return 0;
}
In this program, we implement a queue using two stacks, stack1 and
stack2. The enqueue operation is straightforward, we simply push the element onto
stack1.
For the dequeue operation, we first check if both stack1 and
stack2 are empty, in which case the queue is empty and we cannot dequeue. If
stack2 is empty, we pop all the elements from stack1 and push them onto
stack2, effectively reversing the order of the elements in 
stack1. Finally, we pop the top element from stack2 and return it.
This approach ensures that the first element to be enqueued is always at the bottom of
stack1, which becomes the top element of stack2 after the reversal.

Krishnapriya Rajeev · Answer

We can construct a queue using two stacks and no other temporary variables as such:
Construct a queue structure consisting of two stacks.While enqueuing, push the items to the first stack; they get stored in the reverse order.While dequeuing, pop elements from the first stack and push them to the second stack, so that the order is corrected. We can then pop the topmost element from the second stack.
The space complexity of this algorithm is O(1), as there are no temporary variables.
The time complexity for enqueue operation is O(1), however, the worst-case time complexity for the dequeue operation is O(n), since it requires us to move all elements from one stack to the other.
The code is implemented as follows:
#include andlt;stdio.h>
#include andlt;stdlib.h>
#define SIZE 64
struct Queue{
    int stack1[SIZE];       // 1st stack
    int stack2[SIZE];       // 2nd stack
    int top1,top2;
};
void enqueue(struct Queue* queue, int x){
    queue->stack1[++queue->top1] = x;       // push to 1st stack
}
int dequeue(struct Queue* queue){
    if(queue->top2 == -1){          // if 2nd stack is empty
        while(queue->top1 != -1)
            queue->stack2[++queue->top2] = queue->stack1[queue->top1--];        // pop from 1st stack and push to 2nd stack
    }
    return queue->stack2[queue->top2--];        // pop from 2nd stack
}
int main() {
    struct Queue queue;
    queue.top1 = queue.top2 = -1;
    // Enqueue elements onto queue
    enqueue(andqueue, 5);
    enqueue(andqueue, 10);
    enqueue(andqueue, 15);
    // Dequeue elements from queue
    printf("%d ", dequeue(andqueue));
    printf("%d ", dequeue(andqueue));
    printf("%d ", dequeue(andqueue));
    return 0;
}

forum

Write a program to implement a queue using two stacks.

Utpal Vishwas

Can you answer this question?

2 Answers

Liked By